In certain environments, data, signal, and communication processing resources may be dedicated for use by particular hardware elements, software elements (e.g., application programs), and human operators, each of which may be generally viewed as a "resource user." While such resource dedication is convenient and also ensures that the necessary or otherwise appropriate resources are available whenever the resource user requests them, this one-to-one, dedicated relationship between a resource and a resource user is inefficient. This inefficiency is primarily due to the fact that dedicated resources are most often underutilized since the resource user typically uses its dedicated resource less than 100% of the time.
The present invention employs a more efficient resource allocation approach in which resources are pooled and allocated on an "as needed" basis. In other words, in response to a resource request, a resource (if available) is "withdrawn" from a pool of resources and provided to the requesting resource user. When the resource user is finished using that resource, it is returned to the resource pool. Efficiency is increased because (1) the number of resource users may be considerably larger than the number of resources in the pool and (2) resources are removed from the pool only when they are actually used.
In order for a pooled resource system to work smoothly, the allocation and return of resources from and to the resource pool needs to be managed in an effective and efficient manner. Efficient management is more challenging when the pool of resources as well as the resource requests are not all the same. For instance, one resource request may be for a relatively small resource while another resource request might be for a relatively large resource. Moreover, resource requests may also differ in parameters other than size.
The present invention resolves these issues in part by imposing a structure on the resource pool including specific rules regarding how resources are to be allocated from the pool. Those rules may vary depending on the end application that requests and uses the resources. One example (but non-limiting) structure is the resource hierarchy shown in FIG. 1. The hierarchy includes a plurality of levels or tiers with each level having plural nodes representing a resource block at that level. The data structure is organized in such a way that it "mirrors" the physical resources in terms of how those physical resources are linked or grouped. The physical resources are configured, reconfigured, allocated, de-allocated, organized, and reorganized using the data structure.
The method of the present invention is general with respect to the number of lower level resource units that together forms a higher level resource unit. Level 1 resource blocks correspond as shown in FIG. 1 to one data processing resource unit, where a resource unit may comprise hardware and/or software. Each level 2 resource block corresponds to a group (in this example two) of consecutive level 1 resource blocks. Similarly, each level 3 resource block of the resource hierarchy corresponds to a group of consecutive level 2 resource blocks.
Thus, if a resource request requires four data processing resource units, a single level 3 resource block would be allocated to that request. A level 3 resource block corresponds, in this example, to two level 2 resource blocks which in turn corresponds to four level 1 resource blocks equivalent to the four data processing resource units.
While resources may be allocated from and returned to such a hierarchical structure in random fashion, such an approach may ultimately lead to inefficiencies. In particular, the initial, ordered structure of the resource hierarchy may become fragmented after several resource block allocations and returns. Unfortunately, because of the fragmentation, resource blocks at certain levels cannot be fully utilized. For example, FIG. 2 shows the resource hierarchy of FIG. 1 with a fragmented resource allocation configuration. Circled resource blocks correspond to a currently allocated resource block, and a square enclosing a resource block represents a currently-available resource block. Because level 1 resource block 14 is currently allocated, level 2 resource block 16, logically linked to both level 1 resource blocks 14 and 15, cannot be allocated. A "domino effect" occurs--since level 3 resource block 17 is linked to resource blocks 16 and 18, level 3 resource block 17 cannot be currently allocated even if level 2 resource block 18 were currently available.
On the other hand, if the currently-allocated resource block 19 had been allocated from currently-available resource block 15, the level resource block 18 would have been available for allocation. Similarly, if currently-allocated, level 1 resource block 21 was not allocated, and instead the currently-available level 1 resource block 23 was assigned to the resource request, the currently-unavailable level 2 resource block 21 would be available. The level 2 resource block 21 could then be combined with the level 2 resource block 25 to make available the level 3 resource block 26. Accordingly, as a result of fragmented/inefficient resource allocation at lower levels in the hierarchy, it may be difficult to provide a higher level resource block to a resource request even though there are sufficient, available resources in the resource pool to accommodate the higher level resource request.
Therefore, it is an object of the present invention to overcome this kind of inefficiency by providing a resource pool structure including a data structure reflecting the free resources in the pool and that permits organized and efficient but still flexible allocation and de-allocation of resources.
It is a further object of the present invention to ensure that resource units are evenly utilized in a resource pool.
It is another object of the present invention to selectively re-allocate resources among the resource users to free other resources that can be used to form higher level resource blocks in order to meet a particular resource demand or to simply make available higher level resource blocks.
It is another object of the present invention to determine and implement a resource pool structure data structure, mirroring the free resources in the resource pool, that best suits current resource demands.
The present invention configures a pool of resource units using a logical structure that includes first level and second level resource blocks. The terms "configure resources" or "configuration of resources" refer to a data structure which is organized to reflect or represent actual or physical resources. However, the actual resources themselves are not necessarily configured in a resource hierarchy like that shown in FIG. 1. Each first level resource block corresponds to an individual resource unit, where an individual resource unit is the smallest resource that a resource handler allocates from the resource pool. The first level resource blocks are provided in groups that form a lowest level of the resource pool structure. Each second level resource block corresponds to one of the groups of the first level resource blocks. For example, two first level resource blocks form a first level resource block group logically linked to a second level resource block. The second level resource blocks are provided in groups and form a next higher level of the resource pool structure.
Resources are allocated from the resource unit pool in an efficient manner. For example, if a request is made for a first level resource block, an available first level resource block is allocated from a partially-allocated, first level resource group where one or more first level resource blocks are currently already allocated. If a first resource block is not available, then an available first level resource block is created. In this case, a second level resource block is converted into a corresponding group of first level resource blocks, and one of the converted, first level resource blocks is then allocated to the request. A similar procedure is used at a next higher level, i.e., at third level resource blocks and groupings. In other words, if a first resource block is not available at the first level and cannot be obtained by conversion of a resource block at the second level, a third level resource block is converted into a corresponding group of second level resource blocks; a converted second level resource block is converted into a corresponding group of first level resource blocks; and one of the converted first level resource blocks is allocated.
Resource blocks are also restored to the resource unit pool structure efficiently. For example, a returned first level resource block is restored to a partially-allocated, first level resource block grouping. If that returned block completes that grouping, a new, second level resource block is made available. In one preferred embodiment, when a resource block is restored, the physical resource is restored to the same position in the resource array as from where it was originally allocated. However, the corresponding resource block in the data structure is placed last in a list of free resource blocks. This ensures that each of the physical resources in the pool is used about the same amount over time.
The resource pool is managed by a resource handler which stores in memory a data structure that mirrors the current status (free or occupied) of the resources in the resource pool. The resource pool structure represents and maintains the logical relation between resource units/blocks. For example, the data structure may include multiple lists, each list corresponding to a resource block level and each record/entry in the list representing one free resource unit. The list does not include allocated resource units.
To properly manage the resource unit pool or to otherwise meet a particular a resource request/demand, a resource handler may re-allocate resource units by moving a resource user from one resource block to another at that same level in order to create additional resource blocks at the next higher level. The resource handler may also receive traffic statistics about the number of requests for different level resource blocks collected by a statistics analyzer and determine which level in the resource unit pool structure receives the greatest number of requests, i.e., the most popular level. In an example communication system, assume the system capacity is eight voice calls or two data calls. Most of the calls in the system during busy hours are voice calls. During busy hours, if the whole system capacity is allocated for data calls, no voice calls can be made resulting in an insufficient subscriber service level in the area. By restricting the use of the transmission capacity, at least a minimum level of service for data calls and voice calls can be assured. The resource handler then re-allocates resource units in the current resource pool configuration to create additional resource blocks at the most popular level.
The present invention has particularly advantageous application to communications systems, and in particular, to radio communications systems. A preferred example embodiment of the present invention is disclosed in the context of a wide band, code division multiple access (WCDMA), spread spectrum, radio communications system. Of course, as evident from the above description, the present invention has general applicability and is not limited to communications environments. Various features and advantages of the present invention, some of which have been described above, will be disclosed in further detail in conjunction with the drawings and detailed description.